A hash table may be represented by an array of n elements. Each element e may have one or more locations Le at which it might be found in the table. In typical hashing, Le may consist of a single location. To lookup an element, the location in a hash table Le may be checked to see if the element e is there. If all the locations Le are of some relatively small maximum size, this may be manifestly a constant-time operation.
An insertion operation may be slightly more complex than a lookup operation. One way to perform an insertion may be to remove data from one of the locations Le and insert it someplace else until an open bucket (i.e., a bucket into which the data may fit) is found. Another way may be to perform a search to find a shortest sequence of such removals and insertions that result in an empty space in the original locations Le.
If each Le has exactly two locations, a hashing algorithm may work but may lack good space efficiency. That is, once the hash table is about half full, insertions may fail. An alternative to providing two locations may be to set Le at four. That is, establish that Le is four independent locations within a hash table. This may increase the load factor—that is, increase the number of buckets of the hash table that are filled as compared to the total number of buckets in the hash table—to approximately 97%. To provide for four independent locations, the number of different hash functions applied to a key may be four.
An alternative to establishing that Le is four independent locations may be to establish Le at four dependent locations. Dependent locations can be created by applying any deterministic function to an original location. One way of creating dependent locations is to divide each bucket in the array into two portions, referred to herein as cells. Thus, bucket x may be divided into cells 2x and 2x+1. In this way, the number of hash computations may be two instead of four while establishing Le at 4. This approach of creating dependent locations in a contiguous successive sequence may take advantage of properties of a memory system that make it more efficient to look at consecutive memory locations. Such hash tables may include a load factor of at least 87%.